package problems;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import lib.MathLib;
import lib.Permutations;
import problems.AbstractEuler;

/**
 * The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.
 * Let d_(1) be the 1^(st) digit, d_(2) be the 2^(nd) digit, and so on. In this way, we note the following:
 * 
 * * d_(2)d_(3)d_(4)=406 is divisible by 2
 * * d_(3)d_(4)d_(5)=063 is divisible by 3
 * * d_(4)d_(5)d_(6)=635 is divisible by 5
 * * d_(5)d_(6)d_(7)=357 is divisible by 7
 * * d_(6)d_(7)d_(8)=572 is divisible by 11
 * * d_(7)d_(8)d_(9)=728 is divisible by 13
 * * d_(8)d_(9)d_(10)=289 is divisible by 17
 * 
 * Find the sum of all 0 to 9 pandigital numbers with this property.
 * @author laszlo
 *
 */
public class Euler043 extends AbstractEuler {

	@Override
	/**
	 * an optimization might be to not go through all permutations, but start with only multiples of 17.  
	 */
	public Number calculate() {
		List<String> digits = new LinkedList<String>(Arrays.asList("0", "1", "2", "3", "4", "5", "6", "7", "8", "9"));
		
		long answer = 0;

		Iterator<List<String>> p = new Permutations<String>(digits, digits.size());
		while (p.hasNext()) {
			List<String> next = p.next();
			if (next.get(0).equals("0")) continue;
			StringBuffer strbuf = new StringBuffer();
			for (String digit : next) {
				strbuf.append(digit);
			}
			if (areConsecutiveThreeDigitSubstringsDivisibleByConsecutivePrimes(strbuf)) {
				answer += Long.valueOf(strbuf.toString());
			}
			
		}

		return answer;
	}
	
	private boolean areConsecutiveThreeDigitSubstringsDivisibleByConsecutivePrimes(StringBuffer number) {
		for (int i = 1; i <= 7; i++) {
			long threeDigitSubstring = Long.valueOf(number.substring(i, i + 3));
			if (threeDigitSubstring % MathLib.getPrime(i) != 0) return false;
		}
		
		return true;
	}

	@Override
	protected Number getCorrectAnswer() {
		return 16695334890L;
	}

}
